package com.example.leetcode.leetcode.hot100;

import com.example.leetcode.leetcode.list.ListNode;

/**
 * @author haitao
 * @date 2021/8/27 3:14 下午
 * 判断联表成环（快慢指针）
 * <p>
 * 环形链表 a链表+b环
 * 那么第一次相遇 a 走了 fast， b 走了 slow
 * fast = 2 slow
 * fast = slow + nb
 * 得到 slow = nb
 * 将fast放在head节点走a步，slow在原位置走a步
 * 那么b走过的距离是a+nb步，a+nb一定是在环入口
 */
public class Solution142 {

    public ListNode detectCycle(ListNode head) {
        if (head != null && head.next != null) {
            return null;
        }
        ListNode faster = head, slower = head;
        while (true) {
            if (faster == null || faster.next == null) {
                return null;
            }
            faster = faster.next.next;
            slower = slower.next;
            if (faster == slower) {
                break;
            }
        }
        faster = head;
        while (faster != slower) {
            faster = faster.next;
            slower = slower.next;
        }

        return faster;
    }


}
